package 全排列算法;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;

/**
 * Created by hest0 on 2017/4/21.
 */
public class 全排列 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            ArrayList<String> permutation = Permutation(sc.next());
            for (String x : permutation)
                System.out.println(x);
        }
        sc.close();
    }

    private static ArrayList<String> Permutation(String str) {
        ArrayList<String> al = new ArrayList<>();
        if (str == null || str.length() == 0 || str.length() > 9)
            return al;

        ArrayList<String> sal = str2al(str);
        ArrayList<ArrayList<String>> Perm = calPerm(sal);
        for (int i = 0; i < Perm.size(); i++) {
            al.add(al2str(Perm.get(i)));
        }
        HashSet<String> hs = new HashSet<>(al);

        ArrayList<String> res = new ArrayList<>(hs);
        Collections.sort(res);
        return res;
    }

    private static void calPermRecursion(ArrayList<ArrayList<String>> tal, ArrayList<String> sal, int n) {
        if (n == sal.size()) {
            tal.add(new ArrayList<>(sal));
        } else {
            for (int i = n; i < sal.size(); i++) {
                Collections.swap(sal, i, n);
                calPermRecursion(tal, sal, n + 1);
                Collections.swap(sal, i, n);
            }
        }
    }

    private static ArrayList<ArrayList<String>> calPerm(ArrayList<String> sal) {
        ArrayList<ArrayList<String>> tal = new ArrayList<>();
        calPermRecursion(tal, sal, 0);
        return tal;
    }

    private static ArrayList<String> str2al(String s) {
        ArrayList<String> al = new ArrayList<>();
        for (int i = 0; i < s.length(); i++)
            al.add(String.valueOf(s.charAt(i)));
        return al;
    }

    private static String al2str(ArrayList<String> al) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < al.size(); i++)
            sb.append(al.get(i));
        return sb.toString();
    }
}
